package com.wc.alorithm.string.suffixAutomaton;

import java.util.Scanner;

/**
 * @Author congege
 * @Description
 * @Date Created in 2023/12/12-14:33
 */
public class Main {
    static int maxN = 2100000;

    static class Node {
        int fa, len;
        int[] ch = new int[26];
    }

    static class Edge {
        int next;
        int to;
    }

    static Node[] tree = new Node[maxN];
    static char[] str = new char[maxN];
    static int tot = 1, last = 1;
    static long ans;
    static int[] head = new int[maxN];
    static int cnt;
    static Edge[] edges = new Edge[maxN << 1];
    static long[] f = new long[maxN];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        str = sc.nextLine().toCharArray();
        tree[1] = new Node();
        for (int i = 0; i < str.length; i++) {
            insert(str[i] - 'a');
        }
        for (int i = 2; i <= tot; i++) {
            // 构建绿边
            add(tree[i].fa, i);
        }
    }

    public static void add(int a, int b) {
        edges[++cnt] = new Edge();
        edges[cnt].next = head[a];
        head[a] = cnt;
        edges[cnt].to = b;
    }

    public static void insert(int c) {

        int p = last, cur = last = ++tot;
        f[tot] = 1;
        tree[cur] = new Node();
        // 构建蓝边
        tree[cur].len = tree[p].len + 1;
        for (; p != 0 && tree[p].ch[c] == 0; p = tree[p].fa) {
            tree[p].ch[c] = cur;
        }
        if (p == 0) {
            tree[cur].fa = 1;
        } else {
            // p.len + 1 == q.len
            int q = tree[p].ch[c];
            if (tree[q].len == tree[p].len + 1) {
                tree[cur].fa = q;
            } else {
                int newQ = ++tot;
                tree[newQ] = tree[q];
                tree[newQ].len = tree[p].len + 1;
                tree[q].fa = newQ;
                tree[cur].fa = newQ;
                // p -> c -> q
                for (; p != 1 && tree[p].ch[c] == q; p = tree[p].ch[c]) {
                    tree[p].ch[c] = newQ;
                }
            }
        }
    }
}
